/*
 * @lc app=leetcode.cn id=1447 lang=cpp
 *
 * [1447] 最简分数
 */

// @lc code=start
class Solution
{
public:
    int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    vector<string> simplifiedFractions(int n)
    {
        vector<string> ans;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                int g = gcd(i, j);
                if (g == 1)
                {
                    ans.push_back(to_string(i) + "/" + to_string(j));
                }
            }
        }

        return ans;
    }
};
// @lc code=end
